Processus de décision Markovien (Markov Decision Process - MDP)

1. Exemple en 1D

L'apprentissage par renforcement est associé aux processus de décision Markovien (Markov Decision Process - MDP). L'environnement, dans lequel l'agent évolue, est définit par un ensemble de variables. Ces variables reflètent l'état de l'environnement à un instant spécifique donné, une action que l'agent peut prendre, la récompense qu'il peut obtenir et la transition. Ces variables permettent de définir le MDP.

Prenons un exemple pour illustrer le concept de MDP.

L'agent se déplace en ligne droite (sur une dimension), qui contient 3 états (positions). Il existe un état de départ S et un trou H sur la gauche duquel il n'y a aucune possibilité de sortir. Ainsi, si le temps s'écoule l'agent reste dans le trou. A l'opposé, il y a l'état objectif G. A l'instar du trou, l'agent ne peut s'échapper de cet état et reste dedans si le temps avance.

On considère ici que les transitions entre les états sont déterministes. Cela signifie si l'agent prend l'action d'aller à gauche, la probabilité de transiter vers l'état qui se trouve sur sa gauche est de 1 (il ne peut pas se tromper de direction).

 
 

 
 

Pour décrire les transitions entre les états, on utilise une table des transitions:  
 

Etat: S	Action: A	Etat suivant: S'	Probabilité de transition	Récompense
0(H)	0(Gauche)	0(H)	1	0
0(H)	1(Droite)	0(H)	1	0
1(Départ)	0(Gauche)	0(H)	1	0
1(Départ)	1(Droite)	2(G)	1	1
2(Objectif)	0(Gauche)	2(G)	1	0
2(Objectif)	1(Droite)	2(G)	1	0

L'agent peut également évoluer dans un environnement stochastique. Cela signifie que les transitions entre les états sont régies par des lois de probabilités. L'agent passera donc d'un état à l'autre en suivant une certaine loi de probabilité. L'utilisation des probabilités permet par exemple de prendre en compte qu'un robot se déplaçant vers la droite puisse effectuer une autre action à cause d'une défaillance.

Dans l'exemple suivant, on considère un MDP dans un environnement stochastique. Lorsque l'agent se trouve dans l'état de départ et qu'il effectue l'action "Gauche", la probabilité qu'il se trouve dans le trou (et donc qu'il aille bien vers la gauche) est de 0.8 et la probabilité qu'il arrive au contraire sur l'objectif est donc de 0.2. Il en va de même lorsqu'il va vers la droite.

 
 

Etat: S	Action: A	Etat suivant: S'	Probabilité de transition	Récompense
0(H)	0(Gauche)	0(H)	1	0
0(H)	1(Droite)	0(H)	1	0
1(Départ)	0(Gauche)	0(H)	0.8	0
1(Départ)	0(Gauche)	2(G)	0.2	1
1(Départ)	1(Droite)	2(G)	0.8	1
1(Départ)	1(Droite)	0(H)	0.2	0
2(Objectif)	0(Gauche)	2(G)	1	0
2(Objectif)	1(Droite)	2(G)	1	0

Les processus de décision Markovien permettent donc de décrire comment les transitions de l'agent s'effectuent entre les états de l'environnement.